package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName MergeSort
 * @Description 归并排序，可以采用自上而下的递归或者自下而上的迭代，本次使用递归（所有递归都可以用迭代重写)
 * @Detail          总结：
 *                      1、递归是会从递归的尽头依次返回，直到分叉点，如左边递归与右边递归的交点
 * @Author MyPC
 * @Date 2020/8/7
 * @Version 1.0
 */
public class MergeSort {
    public static void main(String []args){
        int[] arr = {9,8,7,6,5,4,3,2,1,8,5};
        System.out.println(Arrays.toString(sort(arr,0,arr.length-1)));
    }

    /**
     * 排序
     * @param arr
     * @param left
     * @param right
     */
    public static int[] sort(int []arr,int left,int right){
        // 递归体，如果数组长度为1，直接返回数组，不再进行划分
        if (arr.length < 2) {
            return arr;
        }
        int mid=(left+right)/2;
        //如果数组是奇数，那么去左边数组为偶数，右边数组为奇数
        int[] leftArr=new int[mid+1];
        int[] rightArr=new int[right-mid];
        for (int i=0;i<leftArr.length;i++){
            // 拷贝数据到左边的新数组
            leftArr[i]=arr[i];
        }
        for (int i=0;i<rightArr.length;i++){
            // 拷贝数据到右边的新数组
            rightArr[i]=arr[mid+1+i];
        }
        // 递归合并
        return merge(sort(leftArr, 0, leftArr.length - 1), sort(rightArr, 0, rightArr.length - 1));
    }

    /**
     * 数组合并
     * @param left  排好序的左边数组
     * @param right  排好序的右边数组
     * @return
     */
    public static int[] merge(int[] left,int[] right){
        // 新的数组
        int[] merge=new int[left.length+right.length];
        // 新数组的标志位置，也可以代表元素个数
        int index=0;
        // 左边数组的标志位置
        int l=0;
        // 左边数组的标志位置
        int r=0;
        while (l<left.length && r<right.length){
            if(left[l]<=right[r]){
                // 左边数组元素小于或等于右边数组元素，那么取出左边数组元素，并把标志位右移一位
                merge[index++]=left[l];
                l++;
            }else {
                // 右边数组元素小于或等于左边数组元素，那么取出右边数组元素，并把标志位右移一位
                merge[index++]=right[r];
                r++;
            }
        }
        if(l==left.length){
            // 把未合并的左边数组的元素一起合并到新数组
            for(int i=r;i<right.length;i++){
                merge[index++]=right[i];
            }
        }
        if(r==right.length){
            // 把未合并的右边数组的元素一起合并到新数组
            for(int i=l;i<left.length;i++){
                merge[index++]=left[i];
            }
        }
        return merge;
    }
}
